package fun.coding.leetcode;

public class FindPeakElement {

	public static void main(String[] args) {
		FindPeakElement ins = new FindPeakElement();

		int[] test1 = {1, 2, 3, 2};
		System.out.println(ins.findPeakElement(test1));
	}

	public int findPeakElementIterative(int[] num) {
		int l = 0, r = num.length - 1;
		
		// Iterative of binary search
		while(l<=r) {
			int m = (l+r) >> 1;
			long left = Long.MIN_VALUE;
			long right = Long.MIN_VALUE;
	
			left = m == 0 ? left : num[m-1];
			right = m == num.length-1? right : num[m+1];
	
			if(num[m] > left && num[m] > right) return m;
			if(num[m] > left && num[m] < right) {
				l = m+1;
			} else if(num[m] < left && num[m] > right) {
				r = m-1;
			} else {
				// there should be four cases, this is for [2,1,2]
				l++;
			}
		}
		return -1;
	}


	public int findPeakElement(int[] num) {
		return helper(num, 0, num.length - 1);
	}
	
	private int helper(int[] num, int left, int right) {
		int mid = left + (right - left) / 2;
		
		if ((mid == 0 || num[mid - 1] < num[mid]) && (mid == num.length -1 || num[mid + 1] < num[mid])) {
			return mid;
		}
		
		// Very dedicated implementation.
		if (mid > 0 && num[mid] < num[mid - 1]) {
			return helper(num, left, mid - 1);
		}
		else {
			// when mid == 0, and not match, keep shifting to right, this is for strictly ascending array
			return helper(num, mid + 1, right);
		}
	}
	
	

	// This is linear but still can pass OJ, stupid
	public int findPeakElementLinear(int[] num) {
		if (num == null || num.length == 0) return -1;

		int index = num.length - 1;

		for (int i = 1; i < num.length; i++) {
			if (num[i] < num[i - 1]) {
				index = i - 1;
				break;
			}
		}
		return index;
	}

}
